home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / gas / gassrc04.zoo / hash.c < prev    next >
C/C++ Source or Header  |  1991-01-24  |  30KB  |  982 lines
  1. /* hash.c - hash table lookup strings -
  2.    Copyright (C) 1987 Free Software Foundation, Inc.
  3.  
  4. This file is part of GAS, the GNU Assembler.
  5.  
  6. GAS is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. GAS is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GAS; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20. /*
  21.  * BUGS, GRIPES, APOLOGIA etc.
  22.  *
  23.  * A typical user doesn't need ALL this: I intend to make a library out
  24.  * of it one day - Dean Elsner.
  25.  * Also, I want to change the definition of a symbol to (address,length)
  26.  * so I can put arbitrary binary in the names stored. [see hsh.c for that]
  27.  *
  28.  * This slime is common coupled inside the module. Com-coupling (and other
  29.  * vandalism) was done to speed running time. The interfaces at the
  30.  * module's edges are adequately clean.
  31.  *
  32.  * There is no way to (a) run a test script through this heap and (b)
  33.  * compare results with previous scripts, to see if we have broken any
  34.  * code. Use GNU (f)utilities to do this. A few commands assist test.
  35.  * The testing is awkward: it tries to be both batch & interactive.
  36.  * For now, interactive rules!
  37.  */
  38.  
  39. /*
  40.  *  The idea is to implement a symbol table. A test jig is here.
  41.  *  Symbols are arbitrary strings; they can't contain '\0'.
  42.  *    [See hsh.c for a more general symbol flavour.]
  43.  *  Each symbol is associated with a char*, which can point to anything
  44.  *  you want, allowing an arbitrary property list for each symbol.
  45.  *
  46.  *  The basic operations are:
  47.  *
  48.  *    new                     creates symbol table, returns handle
  49.  *    find (symbol)           returns char*
  50.  *    insert (symbol,char*)   error if symbol already in table
  51.  *    delete (symbol)         returns char* if symbol was in table
  52.  *    apply                   so you can delete all symbols before die()
  53.  *    die                     destroy symbol table (free up memory)
  54.  *
  55.  *  Supplementary functions include:
  56.  *
  57.  *    say                     how big? what % full?
  58.  *    replace (symbol,newval) report previous value
  59.  *    jam (symbol,value)      assert symbol:=value
  60.  *
  61.  *  You, the caller, have control over errors: this just reports them.
  62.  *
  63.  *  This package requires malloc(), free().
  64.  *  Malloc(size) returns NULL or address of char[size].
  65.  *  Free(address) frees same.
  66.  */
  67.  
  68. /*
  69.  *  The code and its structures are re-enterent.
  70.  *  Before you do anything else, you must call hash_new() which will
  71.  *  return the address of a hash-table-control-block (or NULL if there
  72.  *  is not enough memory). You then use this address as a handle of the
  73.  *  symbol table by passing it to all the other hash_...() functions.
  74.  *  The only approved way to recover the memory used by the symbol table
  75.  *  is to call hash_die() with the handle of the symbol table.
  76.  *
  77.  *  Before you call hash_die() you normally delete anything pointed to
  78.  *  by individual symbols. After hash_die() you can't use that symbol
  79.  *  table again.
  80.  *
  81.  *  The char* you associate with a symbol may not be NULL (0) because
  82.  *  NULL is returned whenever a symbol is not in the table. Any other
  83.  *  value is OK, except DELETED, #defined below.
  84.  *
  85.  *  When you supply a symbol string for insertion, YOU MUST PRESERVE THE
  86.  *  STRING until that symbol is deleted from the table. The reason is that
  87.  *  only the address you supply, NOT the symbol string itself, is stored
  88.  *  in the symbol table.
  89.  *
  90.  *  You may delete and add symbols arbitrarily.
  91.  *  Any or all symbols may have the same 'value' (char *). In fact, these
  92.  *  routines don't do anything with your symbol values.
  93.  *
  94.  *  You have no right to know where the symbol:char* mapping is stored,
  95.  *  because it moves around in memory; also because we may change how it
  96.  *  works and we don't want to break your code do we? However the handle
  97.  *  (address of struct hash_control) is never changed in
  98.  *  the life of the symbol table.
  99.  *
  100.  *  What you CAN find out about a symbol table is:
  101.  *    how many slots are in the hash table?
  102.  *    how many slots are filled with symbols?
  103.  *    (total hashes,collisions) for (reads,writes) (*)
  104.  *  All of the above values vary in time.
  105.  *  (*) some of these numbers will not be meaningful if we change the
  106.  *  internals.
  107.  */
  108.  
  109. /*
  110.  *  I N T E R N A L
  111.  *
  112.  *  Hash table is an array of hash_entries; each entry is a pointer to a
  113.  *  a string and a user-supplied value 1 char* wide.
  114.  *
  115.  *  The array always has 2 ** n elements, n>0, n integer.
  116.  *  There is also a 'wall' entry after the array, which is always empty
  117.  *  and acts as a sentinel to stop running off the end of the array.
  118.  *  When the array gets too full, we create a new array twice as large
  119.  *  and re-hash the symbols into the new array, then forget the old array.
  120.  *  (Of course, we copy the values into the new array before we junk the
  121.  *  old array!)
  122.  *
  123.  */
  124.  
  125. #include <stdio.h>
  126. #define TRUE           (1)
  127. #define FALSE          (0)
  128. #include <ctype.h>
  129. #define min(a, b)    ((a) < (b) ? (a) : (b))
  130.  
  131. #include "hash.h"
  132. char *xmalloc();
  133.  
  134. #define DELETED     ((char *)1)    /* guarenteed invalid address */
  135. #define START_POWER    (11)    /* power of two: size of new hash table *//* JF was 6 */
  136. /* JF These next two aren't used any more. */
  137. /* #define START_SIZE    (64)    / * 2 ** START_POWER */
  138. /* #define START_FULL    (32)      / * number of entries before table expands */
  139. #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
  140.                 /* above TRUE if a symbol is in entry @ ptr */
  141.  
  142. #define STAT_SIZE      (0)      /* number of slots in hash table */
  143.                 /* the wall does not count here */
  144.                 /* we expect this is always a power of 2 */
  145. #define STAT_ACCESS    (1)    /* number of hash_ask()s */
  146. #define STAT__READ     (0)      /* reading */
  147. #define STAT__WRITE    (1)      /* writing */
  148. #define STAT_COLLIDE   (3)    /* number of collisions (total) */
  149.                 /* this may exceed STAT_ACCESS if we have */
  150.                 /* lots of collisions/access */
  151. #define STAT_USED      (5)    /* slots used right now */
  152. #define STATLENGTH     (6)    /* size of statistics block */
  153. #if STATLENGTH != HASH_STATLENGTH
  154. Panic! Please make #include "stat.h" agree with previous definitions!
  155. #endif
  156.  
  157. /* #define SUSPECT to do runtime checks */
  158. /* #define TEST to be a test jig for hash...() */
  159.  
  160. #ifdef TEST            /* TEST: use smaller hash table */
  161. #undef  START_POWER
  162. #define START_POWER (3)
  163. #undef  START_SIZE
  164. #define START_SIZE  (8)
  165. #undef  START_FULL
  166. #define START_FULL  (4)
  167. #endif
  168.  
  169. /*------------------ plan ---------------------------------- i = internal
  170.  
  171. struct hash_control * c;
  172. struct hash_entry   * e;                                                    i
  173. int                   b[z];     buffer for statistics
  174.                       z         size of b
  175. char                * s;        symbol string (address) [ key ]
  176. char                * v;        value string (address)  [datum]
  177. boolean               f;        TRUE if we found s in hash table            i
  178. char                * t;        error string; "" means OK
  179. int                   a;        access type [0...n)                         i
  180.  
  181. c=hash_new       ()             create new hash_control
  182.  
  183. hash_die         (c)            destroy hash_control (and hash table)
  184.                                 table should be empty.
  185.                                 doesn't check if table is empty.
  186.                                 c has no meaning after this.
  187.  
  188. hash_say         (c,b,z)        report statistics of hash_control.
  189.                                 also report number of available statistics.
  190.  
  191. v=hash_delete    (c,s)          delete symbol, return old value if any.
  192.     ask()                       NULL means no old value.
  193.     f
  194.  
  195. v=hash_replace   (c,s,v)        replace old value of s with v.
  196.     ask()                       NULL means no old value: no table change.
  197.     f
  198.  
  199. t=hash_insert    (c,s,v)        insert (s,v) in c.
  200.